//
// Created by lwj12 on 24-9-7.
//

#ifndef HASHTABLE_HASHTABLE_H
#define HASHTABLE_HASHTABLE_H
#include <vector>
#include <list>
#include <iostream>
using namespace std;
template<class K>
struct HashFunc
{
    size_t operator()(const K& key)
    {
        return (size_t)key;
    }
};

// 特化
template<>
struct HashFunc<string>
{
    size_t operator()(const string& s)
    {
        size_t hash = 0;
        for (auto e : s)
        {
            hash += e;
            hash *= 131;
        }

        return hash;
    }
};

namespace lwj
{
    template<class T>
    struct HTNode
    {
        T _date;
        HTNode* _next;

        HTNode(const T& date = T())
            : _date(date),
              _next(nullptr)
        {}
    };

    template<class K, class T, class Ptr, class Ref, class KeyOfT, class hash>
    struct HashIterator;

    template<class K, class T, class KeyOfT, class hash>
    class HashTable;

    template<class K, class T, class Ptr, class Ref, class KeyOfT, class hash>
    struct HashIterator
    {
        HTNode<T>* _node;
        HashTable<K, T, KeyOfT, hash>* _pht;
        HashIterator(HTNode<T>* node, HashTable<K, T, KeyOfT, hash>* pht)
            :_node(node)
            ,_pht(pht)
        {}

        HashIterator& operator++()
        {
            if(_node->_next) _node = _node->_next;
            else
            {
                hash hs;
                KeyOfT kot;
                size_t sz = _pht->_ht.size();
                size_t hashi = hs(kot(_node->_date)) % sz;
                while(++hashi != sz) if(_pht->_ht[hashi]) _node = _pht->_ht[hashi];
                if(hashi == sz) _node = nullptr;
            }
            return *this;
        }

        HashIterator operator++(int)
        {
            HTNode<T> node = _node;
            if(_node->_next) _node = _node->_next;
            else
            {
                hash hs;
                KeyOfT kot;
                size_t sz = _pht->_ht.size();
                size_t hashi = hs(kot(_node->_date)) % sz;
                while(++hashi != sz) if(_pht->_ht[hashi]) _node = _pht->_ht[hashi];
                if(hashi == sz) _node = nullptr;
            }
            return node;
        }

        HashIterator& operator--()
        {
            hash hs;
            KeyOfT kot;
            size_t sz = _pht->_ht.size();
            size_t hashi = hs(kot(_node->_date)) % sz;
            HTNode<T>* cur;
            if(_pht->_ht[hashi] == _node)
            {
                while(--hashi >= 0)
                {
                    if(_pht->_ht[hashi])
                    {
                        cur =_pht->_ht[hashi];
                        while (cur->_next) cur = cur->_next;
                        _node = cur;
                    }
                }
                if(hashi < 0) _node = nullptr;
            }
            else
            {
                cur = _pht->_ht[hashi];
                while(cur->_next != _node) cur = cur->_next;
                _node = cur;
            }
            return _node;
        }

        HashIterator operator--(int)
        {
            HTNode<T> node = _node;
            hash hs;
            KeyOfT kot;
            size_t sz = _pht->_ht.size();
            size_t hashi = hs(kot(_node->_date)) % sz;
            HTNode<T>* cur;
            if(_pht->_ht[hashi] == _node)
            {
                while(--hashi >= 0)
                {
                    if(_pht->_ht[hashi])
                    {
                        cur = _pht->_ht[hashi];
                        while (cur->_next) cur = cur->_next;
                        _node = cur;
                    }
                }
                if(hashi < 0) _node = nullptr;
            }
            else
            {
                cur = _pht->_ht[hashi];
                while(cur->_next != _node) cur = cur->_next;
                _node = cur;
            }
            return node;
        }

        Ref operator*() {return _node->_date;}
        Ptr operator->() {return &_node->_date;}

        bool operator==(const HashIterator& it) {return _node == it._node;}
        bool operator!=(const HashIterator& it) {return !operator==(it);}
    };

    template<class K, class T, class KeyOfT, class hash>
    class HashTable
    {
    public:
        friend struct HashIterator<K, T, class Ptr, class Ref, KeyOfT, hash>;
        typedef HashIterator<K, T, T*, T&, KeyOfT, hash> iterator;
        typedef HashIterator<K, T, const T*, const T&, KeyOfT, hash> const_iterator;

        iterator begin()
        {
            int i = -1;
            while(++i != _ht.size())
            {
                if(_ht[i]) return iterator(_ht[i], this);
            }
        }

        const_iterator end() const {return {nullptr, this};}

        const_iterator begin() const
        {
            int i = -1;
            while(++i != _ht.size())
            {
                if(_ht[i]) return iterator(_ht[i], this);
            }
        }

        iterator end() {return {nullptr, this};}

        HashTable()
        {
            _ht.resize(10, nullptr);
            _sz = 0;
        }

        ~HashTable()
        {
            HTNode<T>* cur, *next;
            for(auto e : _ht)
            {
                cur = e;
                while (cur)
                {
                    next = cur->_next;
                    delete cur;
                    cur = next;
                }
            }
            _sz = 0;
        }

        pair<iterator, bool> insert(const T& data)
        {
            KeyOfT kot;
            iterator it = find(kot(data)).first;
            if (it != end())
                return make_pair(it, false);

            hash hs;
            size_t hashi = hs(kot(data)) % _ht.size();

            // 负载因子==1扩容
            if (_sz == _ht.size())
            {
                vector<HTNode<T>*> newtables(_ht.size() * 2, nullptr);
                for (size_t i = 0; i < _ht.size(); i++)
                {
                    HTNode<T>* cur = _ht[i];
                    while (cur)
                    {
                        HTNode<T>* next = cur->_next;

                        // 旧表中节点，挪动新表重新映射的位置
                        hashi = hs(kot(cur->_date)) % newtables.size();
                        // 头插到新表
                        cur->_next = newtables[hashi];
                        newtables[hashi] = cur;

                        cur = next;
                    }

                    _ht[i] = nullptr;
                }

                _ht.swap(newtables);
            }

            // 头插
            HTNode<T>* newnode = new HTNode<T>(data);
            newnode->_next = _ht[hashi];
            _ht[hashi] = newnode;
            ++_sz;

            return make_pair(iterator(newnode, this), true);
        }
        pair<iterator, bool> find(const K& key)
        {
            KeyOfT kot;
            hash func;
            size_t hashi = func(key) % (_ht.size());
            HTNode<T>* cur = _ht[hashi];
            while (cur)
            {
                if(kot(cur->_date) == key) return {iterator(cur,this), true};
                cur = cur->_next;
            }
            return {iterator(nullptr, this), false};
        }

        pair<iterator, bool> erase(const T& date)
        {
            hash func;
            KeyOfT kot;
            size_t key = func(date);
            size_t hashi = key % (_ht.size());
            HTNode<T>* cur = _ht[hashi];
            HTNode<T>* prev = nullptr;
            while (cur)
            {
                if(kot(cur->_date) == key)
                {
                    if(prev) prev->_next = cur->_next;
                    else _ht[hashi] = cur->_next;
                    iterator it(cur, this);
                    delete cur;
                    _sz--;
                    return {it++, true};
                }
                prev = cur;
                cur = cur->_next;
            }
            return {iterator(nullptr, this), false};
        }
    private:
        vector<HTNode<T>*> _ht;
        size_t _sz;
    };
}

#endif//HASHTABLE_HASHTABLE_H
